import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> ans;
    public StringBuffer path;
    public int num;
    int left;
    int right;
    private int rigth;

    public List<String> generateParenthesis(int n) {
        ans=new ArrayList<>();
        path=new StringBuffer();
        num=n;
        dfs();
        return ans;
    }
    public void dfs(){
        if(right==num){
            ans.add(path.toString());
            return;
        }
        if(left<num){
            path.append('(');
            left++;
            dfs();
            left--;
            path.deleteCharAt(path.length()-1);
        }
        if(right<left){
            path.append(')');
            right++;
            dfs();
            rigth--;
            path.deleteCharAt(path.length()-1);
        }
    }
}